/*================================================================
*   文件名称：main.cpp
*   创 建 者：yang qiang
*   创建日期：2018年11月04日
*   描    述：
*   Copyright (C) 2018 All rights reserved.
*   
================================================================*/


#include <iostream>

using namespace std;

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        if( m == 0 || n == 0 )
            return 0;
        //vector<vector<int> > path(m, vector<int> (n, 0));
        int i = m - 2, j = n - 2;
        //path[m-1][n-1] = grid[m-1][n-1];

        for(i; i >= 0; i--)
            grid[i][n-1] += grid[i+1][n-1];
        for( j; j >= 0; j-- )
            grid[m-1][j] += grid[m-1][j+1];

        for( i = m - 2; i >=0; i-- ){
            for( j = n - 2; j >= 0; j-- ){
                grid[i][j] += min(grid[i+1][j], grid[i][j+1]);
            }
        }

        return grid[0][0];
    }
};
